package 剑指offer;

import java.util.Stack;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/25 10:28 星期四
 */
public class _30_包含min函数的栈 {

    public static void main(String[] args) {
        _30_包含min函数的栈 stack = new _30_包含min函数的栈();
        stack.push(-2);
        stack.push(0);
        stack.push(-3);
        System.err.println(stack.min());
        stack.pop();
        stack.pop();
        System.err.println(stack.min());
    }

    /**
     * 链表实现栈
     * 定义最小值法，当删除元素恰好是最小值或初始化时，将min初始化为Integer.MAX_VALUE即最大值
     * > 2022/08/25 11:05:36
     * 解答成功:
     * 	执行耗时:12 ms,击败了97.48% 的Java用户
     * 	内存消耗:43.6 MB,击败了30.52% 的Java用户
     */

    private int min;
    private Node head;
    private int N;

    /**
     * initialize your data structure here.
     */
    public _30_包含min函数的栈() {
        min = Integer.MAX_VALUE;
        head = new Node();
        N = 0;
    }

    public void push(int x) {
        //入栈，入栈前比较最小值
        min = Math.min(x, min);
        //让头结点的第一个有效位指向新结点，新结点指向head之前的下一结点
        head.next = new Node(x,head.next);
    }

    //出栈
    public void pop() {
        if (head.next == null){
            //空栈直接return
            return;
        }
        //记录栈顶元素值
        int val = head.next.val;
        //删除
        head.next = head.next.next;
        //若删除元素就是min
        if (val == min){
            //重置最小值为最大值
            min = Integer.MAX_VALUE;
            //遍历剩余结点，找最小值赋值给min，保证min为最小值
            Node n = head.next;
            while (n != null){
                min = Math.min(n.val,min);
                n = n.next;
            }
        }
    }

    //返回栈顶元素，可能空指针，但是int类型...不知道反回啥
    public int top() {
        return head.next.val;
    }

    public int min() {
        return min;
    }

    //结点类
    static class Node{
        Node next;
        int val;

        public Node(){}

        public Node(int val){
            this.val = val;
        }

        public Node(int val,Node next){
            this.val = val;
            this.next = next;
        }

    }
}
